﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习八月份
{
    public class DLinkedListNode
    {

        public int key;
        public int val;
        public DLinkedListNode pre;
        public DLinkedListNode next;
        public DLinkedListNode(int key=0, int val=0, DLinkedListNode pre=null, DLinkedListNode next=null)
        {
            this.key = key;
            this.val = val;
            this.pre = pre;
            this.next = next;

        }


    }




        public class LRUCache
    {


        //双向链表
        DLinkedListNode dummyhead=new DLinkedListNode();
         Dictionary<int, DLinkedListNode> map = new Dictionary<int, DLinkedListNode>();
        int count = 0;
        int _capacity = 0;
        public LRUCache(int capacity)
        {
            dummyhead.next = dummyhead;
            dummyhead.pre = dummyhead;
            _capacity=capacity;
        }

        public int Get(int key)
        {
            if (map.ContainsKey(key))
            {
                DLinkedListNode cur = map[key];

                MoveToHead(cur);

                return cur.val;
            }
            else
            {
                return -1;
            }
            


        }

      
        public void Put(int key, int value)
        {

            

            if (map.ContainsKey(key))
            {
                DLinkedListNode cur = map[key];
                cur.val = value;

                MoveToHead(cur);

                
            }
            else
            {


                if(count==_capacity)
                {
                    DLinkedListNode last = dummyhead.pre;


                    DeleteNode(last);
                    int lastkey=last.key;
                    map.Remove(lastkey);
                    count--;

                }
                DLinkedListNode newNode = new DLinkedListNode(key, value);
                map[key] = newNode;
                AddToHead(newNode);
                count++;
            }
          



        }
        private void MoveToHead(DLinkedListNode cur)
        {

            DeleteNode(cur);
            AddToHead(cur);

        }

        private void DeleteNode(DLinkedListNode cur)
        {
         
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;

        }

        private void AddToHead(DLinkedListNode newNode)
        {
            newNode.next = dummyhead.next;   
            dummyhead.next= newNode;
            newNode.next.pre = newNode;
            newNode.pre= dummyhead;


        }
    }

    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.Get(key);
     * obj.Put(key,value);
     */
}
